package com.LeeCode;

/**
 * 山脉数组中查找目标值
 */

public class Code1095 {
    public static void main(String[] args) {

    }

    public int findInMountainArray(int target, MountainArray mountainArr) {
        int n = mountainArr.length();
        int peekIndex = findPeek(mountainArr);

        int num = mountainArr.get(peekIndex);
        if (num == target) {
            return peekIndex;
        }

        int index = binarySearch(mountainArr, -1, peekIndex, target, true);

        if (index < peekIndex && mountainArr.get(index) == target)
            return index;

        index = binarySearch(mountainArr, peekIndex, n, target, false);

        if (index < n && mountainArr.get(index) == target)
            return index;

        return -1;
    }

    private int findPeek(MountainArray mountainArr) {
        int left = 0, right = mountainArr.length();
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (mountainArr.get(mid) > mountainArr.get(mid + 1)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }

    private int binarySearch(MountainArray mountainArr, int left, int right, int target, boolean ascend) {
        if (ascend) {
            while (left + 1 < right) {
                int mid = left + (right - left) / 2;
                int num = mountainArr.get(mid);
                if (num == target) {
                    return mid;
                } else if (num > target) {
                    right = mid;
                } else {
                    left = mid;
                }
            }
            return right;
        } else {
            while (left + 1 < right) {
                int mid = left + (right - left) / 2;
                int num = mountainArr.get(mid);
                if (num == target) {
                    return mid;
                } else if (num > target) {
                    left = mid;
                } else {
                    right = mid;
                }
            }
            return left;
        }

    }

    class MountainArray {
        public int get(int index) {
            return 0;
        }

        public int length() {
            return 0;
        }
    }
}
